package leetcode.p518;

/**
 * 零钱兑换
 *
 * @author: trtan
 * @date: 2021-06-10 19:25
 **/
public class CoinChangeTwo {
    public static void main(String[] args) {
        int amount = 5;
        int[] coins = new int[]{1, 2, 5};
        System.out.println(new CoinChangeTwo().change(amount, coins));
        System.out.println(new CoinChangeTwo().changeBetter(amount, coins));
        System.out.println(new CoinChangeTwo().bestChange(amount, coins));
    }
    public int change(int amount, int[] coins) {
        // dp[i][j] 代表前i种硬币凑成j的方案数
        int[][] dp = new int[coins.length + 1][amount + 1];
        // 0种硬币凑成0方案数为1
        dp[0][0] = 1;
        for (int i = 1; i <= coins.length; i++) {
            int val = coins[i - 1];
            for (int j = 0; j <= amount; j++) {
                for (int k = 0; k * val <= j; k++) {
                    //前i种硬币和为j的方案可以由前i-1种硬币转移过来，第i种硬币数量为k
                    dp[i][j] += dp[i - 1][j - k * val];
                }
            }
        }
        return dp[coins.length][amount];
    }

    public int changeBetter(int amount, int[] coins) {
        //去掉一维，dp[i]代表凑成j的方案数
        int[] dp = new int[amount + 1];
        //凑成0只有一种方案
        dp[0] = 1;
        for (int i = 1; i <= coins.length; i++) {
            int val = coins[i - 1];
            //从大到小遍历，小的为前i-1时的状态，即保留了i种硬币由i-1种硬币转移过来
            for (int j = amount; j >= 0; j--) {
                for (int k = 1; k * val <= j; k++) {
                    dp[j] += dp[j - k * val];
                }
            }
        }
        return dp[amount];
    }

    public int bestChange(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int i = 1; i <= coins.length; i++) {
            //相比较changeBetter优化 对于任意j都能由j-coins[i - 1]转移过来，由于是从小到大，后面方案会由前面转移过来
            // 即dp[j] += (dp[j - coins[i - 1]]]), 而dp[j - coins[i - 1]] += dp[j - 2 * coins[i - 1]];
            for (int j = coins[i - 1]; j <= amount; j++) {
                dp[j] += dp[j - coins[i - 1]];
            }
        }
        return dp[amount];
    }
}
